package sort.yht;

import sort.util.Constants;
import sort.util.MySort;

/**
 * 功能描述：桶排序
 * @Author: yht
 * @Date: 2021/8/11 14:14
 */
public class Tong implements MySort {

  @Override
  public String getName() {
    return "【桶排序】";
  }

  @Override
  public int[] sort(int[] a) {
    //计算桶数量（以平均每个桶装100个数据为准）
    final int tongSize = Constants.TONG_AVG_SIZE*Constants.TONG_INIT_SIZE_EXP;
    final int tongAmount = Constants.MAX_ARR_SIZE/Constants.TONG_AVG_SIZE;//桶数量
    final int range = Constants.MAX_DATA_VALUE/tongAmount;//桶数据值跨度
    int [][] tongs = new int[tongAmount][tongSize];
    int [] jishu = new int[tongAmount];
    //先把数据都放到桶里边
    for(int m : a)
      tongs[m/range][jishu[m/range]++] = m+range;
    //再把桶里边有效数据装回去
    int index = 0;
    for(int [] tong : tongs) {
      int k = -1;
      while (tong[k+1] > 0) k++;
      if(k > -1) {
        //对桶内数据快速排序
        KuaiSu.doSort(tong, 0, k);
        //把桶内数据装回原数组
        for(int m = 0; m <= k; m++)
          a[index++] = tong[m]-range;
      }
    }
    return a;
  }

  public static void main(String[] args) {
    new Tong().testAll();
  }
}
